home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / prio / _eb_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  14.3 KB  |  715 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _eb_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/impl/eb_tree.h>
  18.  
  19. // Stefan  Naeher ( 1989 )
  20. // Michael Wenzel ( 1990 ) 
  21.  
  22.  
  23.  
  24. // ----------------------------------------------------------
  25. //
  26. // Konstruktor & Destruktor
  27. //
  28.  
  29. l_stratified::l_stratified(stratified_ptr b, int x)
  30. {
  31.   int t = b->min2();
  32.  
  33.   if ( x == b->min() )
  34.   {
  35.     ma = t;
  36.     mi = b->max();
  37.   }
  38.  
  39.   if ( x == t )
  40.   {
  41.     ma = b->min();
  42.     mi = b->max();
  43.   }
  44.  
  45.   if ( x == b->max() )
  46.   {
  47.     ma = b->min();
  48.     mi = t;
  49.   }
  50.  
  51. }
  52.  
  53.  
  54. stratified::stratified(int i)  
  55. { 
  56.  
  57.   mi = ma = -1;
  58.   sz = 0; 
  59.   k = i;
  60.   top = 0;
  61.   bot = 0;
  62.  
  63. }
  64.  
  65. stratified::stratified(l_stratified_ptr l, int i)
  66. { 
  67.  
  68.   mi = l->min();
  69.   ma = l->max();
  70.   sz = 2;
  71.   k = i;
  72.   top = 0;
  73.   bot = 0;
  74.  
  75. }
  76.  
  77.  
  78. stratified::~stratified()  
  79. { 
  80.                                          // deallocate memory of sub-structures
  81.   if ((k>1) && (sz>2))
  82.   {                                      // delete stratified trees of bot
  83.     bot->clear(k);
  84.  
  85.     if ( k <= 8 )
  86.       delete bot->l;
  87.     else
  88.       delete bot->d;
  89.     delete bot;
  90.  
  91.     if ( top->size() <= 2 )
  92.       delete top;
  93.     else
  94.       delete (stratified_ptr)top;
  95.  
  96.     top = 0;
  97.     bot = 0;
  98.  
  99.   }
  100.  
  101. }
  102.  
  103. // ----------------------------------------------------------
  104. //
  105. // min2                  
  106. //
  107. // liefert 2. kleinstes Element, falls sz > 2
  108. //
  109. // -1 , sonst
  110. //
  111. // ----------------------------------------------------------
  112.  
  113. int stratified::min2()
  114.  
  115. {
  116.   if ( sz < 3 )
  117.     return -1;
  118.  
  119.   int z = top->min();
  120.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(bot->lookup(z,k));
  121.  
  122.   return (mal_pot_2(z,down(k))) | (l_bot_ptr->min());
  123.  
  124. }
  125.  
  126.  
  127. // ----------------------------------------------------------
  128. //
  129. // max2                  
  130. //
  131. // liefert 2. groesstes Element, falls sz > 2
  132. //
  133. // -1 , sonst
  134. //
  135. // ----------------------------------------------------------
  136.  
  137. int stratified::max2()
  138.  
  139. {
  140.   if ( sz < 3 )
  141.     return -1;
  142.  
  143.   int z = top->max();
  144.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(bot->lookup(z,k));
  145.  
  146.   return (mal_pot_2(z,down(k))) | (l_bot_ptr->max());
  147.  
  148. }
  149.  
  150.  
  151. // ----------------------------------------------------------
  152. //
  153. // succ                  
  154. //
  155. // liefert Nachfolger von x im Baum auf dieser Rekursionsstufe
  156. //                    falls existiert
  157. // -1 , sonst
  158. //
  159. // ----------------------------------------------------------
  160.  
  161. int stratified::succ(int x) 
  162.  
  163. {
  164.   if ( x >= ma ) return -1;
  165.   if ( x <  mi ) return mi;
  166.   if ( sz == 2 ) return ma;               // mi < x < ma
  167.  
  168.                                           // sz >= 2 &&  k>1
  169.   int x1 = high_bits(x); 
  170.   int x2 = low_bits(x); 
  171.  
  172.   GenPtr p = bot->lookup(x1,k);
  173.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(p);
  174.  
  175.   if ( (l_bot_ptr) && (l_bot_ptr->max()>x2) )
  176.   { 
  177.     if ( l_bot_ptr->size() <= 2 )             // l_stratified Struktur
  178.         return ( mal_pot_2(x1,down(k))) | ( l_bot_ptr->succ(x2) ) ;
  179.     else
  180.     {
  181.       stratified_ptr bot_ptr = stratified_ptr(p) ;
  182.       return (mal_pot_2(x1,down(k))) | (bot_ptr->succ(x2)) ;
  183.     }
  184.   }
  185.   else                                   // succ nicht in bot-Unterstruktur
  186.   {
  187.     int z;
  188.     
  189.     if ( top->size() <= 2 )
  190.       z = top->succ(x1); 
  191.     else
  192.       z = ((stratified_ptr)top)->succ(x1); 
  193.  
  194.     if ( z == -1 ) 
  195.       return ma;                         // x unmittelbar vor Maximum
  196.  
  197.     l_stratified_ptr l_bot_ptr = l_stratified_ptr(bot->lookup(z,k));
  198.  
  199.     return (mal_pot_2(z,down(k))) | (l_bot_ptr->min()) ;
  200.   }
  201.  
  202. }
  203.  
  204. // ----------------------------------------------------------
  205. //
  206. // pred                  
  207. //
  208. // liefert Vorgaenger von x im Baum auf dieser Rekursionsstufe
  209. //                    falls existiert
  210. // -1 , sonst
  211. //
  212. // ----------------------------------------------------------
  213.  
  214. int stratified::pred(int x) 
  215.  
  216. {
  217.   if ( x >  ma ) return ma;
  218.   if ( x <= mi ) return -1;
  219.   if ( sz == 2 ) return mi;               // mi < x < ma
  220.  
  221.                       // sz > 2 && k > 1
  222.   int x1 = high_bits(x); 
  223.   int x2 = low_bits(x); 
  224.  
  225.   GenPtr p = bot->lookup(x1,k);
  226.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(p);
  227.  
  228.   if ( (l_bot_ptr) && (l_bot_ptr->min()<x2) ) 
  229.   {
  230.     if ( l_bot_ptr->size() <= 2 )             // l_stratified Struktur
  231.         return ( mal_pot_2(x1,down(k))) | ( l_bot_ptr->pred(x2) ) ;
  232.     else
  233.     {
  234.       stratified_ptr bot_ptr = stratified_ptr(p) ;
  235.       return (mal_pot_2(x1,down(k))) | (bot_ptr->pred(x2)) ;
  236.     }
  237.   }
  238.  
  239.   else                                        // pred nicht in top-Unterstruktur
  240.     
  241.   {
  242.     int z;
  243.  
  244.     if ( top->size() <= 2 )
  245.       z = top->pred(x1); 
  246.     else
  247.       z = ((stratified_ptr)top)->pred(x1); 
  248.  
  249.     if ( z == -1 ) 
  250.       return mi;                              // x unmittelbar vor Maximum
  251.  
  252.     l_stratified_ptr l_bot_ptr = l_stratified_ptr(bot->lookup(z,k));
  253.  
  254.     return (mal_pot_2(z,down(k))) | (l_bot_ptr->max() ) ;
  255.   }
  256.  
  257. } 
  258.  
  259. // --------------------------------------------------------------- 
  260. //
  261. // member   
  262. //
  263. // liefert 1, falls Element in der Struktur
  264. //
  265. //         0, sonst
  266. //
  267. // ----------------------------------------------------------
  268.  
  269. int stratified::member(int x)
  270. { 
  271.   if (( x == ma )||( x == mi ))
  272.     return 1;
  273.  
  274.   if (( x < mi )||( x > ma ))
  275.     return 0;
  276.  
  277.   if ( sz == 2 )
  278.     return 0;
  279.  
  280.                      // sz > 2 && k > 1
  281.   int x1 = high_bits(x); 
  282.   int x2 = low_bits(x); 
  283.  
  284.   GenPtr p = bot->lookup(x1,k);
  285.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(p);
  286.  
  287.   if (l_bot_ptr)
  288.  
  289.     if ( l_bot_ptr->size() <= 2 )    // l_stratified Struktur
  290.       return l_bot_ptr->member(x2);
  291.  
  292.     else
  293.     {
  294.       stratified_ptr bot_ptr = stratified_ptr(p);
  295.       return bot_ptr->member(x2);                  
  296.     }
  297.  
  298.   else
  299.     return 0;                
  300.  
  301. }
  302.  
  303. // ----------------------------------------------------------
  304. //
  305. // insert           
  306. //
  307. // fuegt ein Element x rekursiv in den Baum ein
  308. //
  309. // liefert 1, falls es eingefuegt wurde
  310. //
  311. //         0, falls es schon Element dewr Struktur war
  312. //
  313. // ----------------------------------------------------------
  314.  
  315. int stratified::insert(int x)
  316. { 
  317.   int inserted = 0;
  318.  
  319.   if ( ( x == mi ) || ( x == ma ) )      // Element in Structure
  320.     return 0;
  321.  
  322.   switch (sz)
  323.   {
  324.  
  325.     case 0: 
  326.          {
  327.            mi = ma = x;
  328.  
  329.            inserted = 1;
  330.                break;
  331.              }
  332.  
  333.     case 1:
  334.          {                           // incremental construction iff sz > 2
  335.                if ( x > mi ) 
  336.              ma = x;
  337.            else
  338.              mi = x;
  339.  
  340.            inserted = 1;
  341.                break;
  342.              }
  343.  
  344.     default: {                           // => k>1
  345.  
  346.            if ( x > ma )
  347.            { 
  348.          int t = ma;
  349.          ma = x;
  350.          x = t;
  351.                }
  352.          
  353.                if ( x < mi )
  354.            { 
  355.          int t = mi;
  356.          mi = x;
  357.          x = t;
  358.                }
  359.  
  360.                int x1 = high_bits(x);
  361.                int x2 = low_bits(x);
  362.  
  363.                                          // for incremental construction
  364.  
  365.                if ( top == 0 )           // allocate new structures
  366.                { 
  367.              top = new l_stratified(); 
  368.                  bot = new b_dict(k);
  369.                }          
  370.  
  371.                GenPtr& p = bot->lookup(x1,k);
  372.                l_stratified_ptr l_bot_ptr = l_stratified_ptr(p);
  373.  
  374.            if ( l_bot_ptr )
  375.                {
  376.                  if ( l_bot_ptr->size() == 1 )
  377.            inserted = l_bot_ptr->insert(x2);
  378.          else
  379.                  {
  380.            stratified_ptr bot_ptr;
  381.  
  382.            if ( l_bot_ptr->size() == 2 ) 
  383.                    {
  384.              if ( !l_bot_ptr->member(x2) ) 
  385.                      {
  386.                bot_ptr = new stratified(l_bot_ptr,down(k));
  387.                        inserted = bot_ptr->insert(x2);
  388.  
  389.                p = (GenPtr)bot_ptr;
  390.  
  391.                delete l_bot_ptr;
  392.                      }
  393.                    }
  394.            else       // l_bot_ptr was a bot_ptr
  395.                    {
  396.                      bot_ptr = stratified_ptr(p) ;
  397.                      inserted = bot_ptr->insert(x2);
  398.                    }
  399.                  }
  400.  
  401.                }
  402.                else                // no top entry 
  403.            {
  404.                  l_bot_ptr = new l_stratified(x2);
  405.  
  406.          if ( top->size() <= 1 )
  407.            top->insert(x1);
  408.                  else
  409.                  { 
  410.            stratified_ptr ntop;
  411.  
  412.            if ( top->size() == 2 )
  413.            { 
  414.              ntop = new stratified(top,up(k));
  415.              delete top;
  416.              top = (l_stratified_ptr)ntop;
  417.                    }
  418.            else
  419.              ntop = (stratified_ptr)top;
  420.  
  421.                ntop->insert(x1);
  422.                  }
  423.  
  424.              GenPtr help = GenPtr(l_bot_ptr);
  425.              bot->insert(x1,help,k);
  426.          inserted = 1;
  427.                }
  428.                break;
  429.              }                           // default case
  430.  
  431.   }                                      // switch
  432.  
  433.   if ( inserted )
  434.     sz++;
  435.  
  436.   return inserted;
  437.  
  438. }
  439.  
  440. // ----------------------------------------------------------
  441. //
  442. // del              
  443. //
  444. // streicht ein Element x rekursiv aus dem Baum 
  445. //
  446. // liefert 1, falls es gestrichen wurde
  447. //
  448. //         0, falls es nicht Element der Struktur war
  449. //
  450. // ----------------------------------------------------------
  451.  
  452. int stratified::del(int x)
  453.  
  454. { 
  455.  
  456.   int deleted = 0;
  457.  
  458.   switch (sz)
  459.   {
  460.  
  461.     case 0 : break;
  462.  
  463.     case 1 :
  464.          { 
  465.                if ( x == mi )
  466.            { 
  467.              mi = ma = -1;
  468.          deleted = 1;
  469.                }
  470.            break;
  471.              }
  472.  
  473.  
  474.  
  475.     case 2 :
  476.              {
  477.                if ( x == mi ) 
  478.                {
  479.              mi = ma;
  480.              deleted = 1;
  481.            }
  482.  
  483.                if ( x == ma )
  484.                {
  485.              ma = mi;
  486.              deleted = 1;
  487.            }
  488.  
  489.            break;
  490.              }
  491.  
  492.     case 3 :       
  493.                                    /* delete incremental construction */
  494.              {           
  495.                int t = min2();     /* third element */
  496.  
  497.                if ( x == mi )      /* new minimum   */
  498.                {
  499.               mi = t;
  500.           deleted = 1;
  501.                }
  502.  
  503.                if ( x == ma )      /* new maximum   */
  504.                {
  505.               ma = t;
  506.           deleted = 1;
  507.                }
  508.  
  509.            if ( x == t )
  510.          deleted = 1;
  511.  
  512.                if ( deleted )
  513.                            /* delete stratified trees of bot  */
  514.                {
  515.                  bot->clear(k);
  516.          if ( k <= 8 )
  517.                    delete bot->l;
  518.                  else
  519.                    delete bot->d;
  520.                  delete bot;
  521.                  bot = 0;
  522.  
  523.                  delete top;
  524.                  top = 0;
  525.                }                   /* incremental construction deleted */
  526.  
  527.            break;
  528.              }         
  529.  
  530.     default :
  531.              {
  532.            l_stratified_ptr l_bot_ptr;
  533.            stratified_ptr bot_ptr;
  534.  
  535.                if ( x == ma )                 /* delete maximum */
  536.                {
  537.          int z = max2();
  538.          ma = z;
  539.              x = z;
  540.                }
  541.  
  542.                if ( x == mi )                /* delete minimum */
  543.                {
  544.          int z = min2();
  545.          mi = z;
  546.              x = z;
  547.                }
  548.  
  549.                int x1 = high_bits(x);
  550.                int x2 = low_bits(x);
  551.  
  552.                GenPtr& p = bot->lookup(x1,k);
  553.  
  554.            if (!p)
  555.          return 0;                  /* element not in structure */
  556.  
  557.                l_bot_ptr = l_stratified_ptr(p) ;
  558.  
  559.                if ( l_bot_ptr->size() <= 2 )
  560.            {
  561.                  deleted = l_bot_ptr->del(x2);
  562.  
  563.                  if ( l_bot_ptr->size() == 0 )  /* delete structure */
  564.              {
  565.                    delete l_bot_ptr;
  566.   
  567.            if ( top->size() <= 2 )
  568.              top->del(x1);
  569.                    else
  570.            {
  571.              stratified_ptr ntop = (stratified_ptr)top;
  572.              if ( ntop->sz == 3 )
  573.              { 
  574.                top = new l_stratified(ntop,x1);
  575.                delete ntop;
  576.                      }
  577.              else
  578.                        ntop->del(x1);
  579.                    } 
  580.  
  581.                    bot->del(x1,k);
  582.                  }
  583.                }
  584.  
  585.                else                                  /* stratified structure */
  586.                {
  587.                  bot_ptr = stratified_ptr(p) ;
  588.  
  589.                  if ( bot_ptr->sz == 3 )              /* change into l_stratified */
  590.                  {
  591.            if ( bot_ptr->member(x2) )
  592.            {
  593.              l_bot_ptr = new l_stratified(bot_ptr,x2);
  594.              deleted = 1;
  595.  
  596.                      p = (GenPtr)l_bot_ptr;
  597.  
  598.                      delete bot_ptr;
  599.  
  600.                    }
  601.                  }
  602.                  else                               /* size >= 4 */
  603.                    deleted = bot_ptr->del(x2);
  604.                }
  605.  
  606.            break;
  607.              }
  608.  
  609.   }
  610.  
  611.   if ( deleted ) 
  612.     sz--;
  613.  
  614.   return deleted;
  615. }
  616.  
  617. // ----------------------------------------------------------
  618. //
  619. // print            
  620. //
  621. // druckt alle Elemente des Baumes aus            
  622. //
  623. // ----------------------------------------------------------
  624.  
  625. void stratified::print()
  626. { 
  627.   int i = -1;
  628.   while ((i=succ(i))>=0)
  629.     cout << i << " ";
  630. }
  631.  
  632. // -------------------------------------------------------
  633. // clear
  634. //
  635. // loescht alle Elemente, zerstoert Unterbaeume und 
  636. // setzt Dictionary auf Leerzustand
  637. //
  638. // ----------------------------------------------------------
  639.  
  640. b_dict::b_dict(int k) 
  641. { if ( k <= 8 ) 
  642.    { l = new GenPtr[pot_2(up(k))];
  643.      for (int i = 0; i < pot_2(up(k)); i++) l[i] = 0;
  644.     }
  645.   else 
  646.    d = new dp_hash;
  647. }
  648.  
  649. void b_dict::clear(int k)
  650. { 
  651.   if ( k <= 8 )
  652.   {
  653.     for (int i = 0; i < pot_2(up(k)); i++)
  654.     { 
  655.       l_stratified_ptr l_bot_ptr=l_stratified_ptr(l[i]);
  656.       if  (l_bot_ptr)
  657.         if (l_bot_ptr->size()<=2) 
  658.           delete l_bot_ptr;
  659.         else
  660.         { 
  661.           stratified_ptr bot_ptr=stratified_ptr(l[i]);
  662.           delete bot_ptr;
  663.         }
  664.     }
  665.  
  666.     return;
  667.   }
  668.       
  669.                                  // b_dict was a hashing structure
  670.  
  671.  
  672.   stp s = new subtable[d->n];
  673.   stp pos = s;
  674.   int i=0;
  675.  
  676.   while (i<d->sM)                        // Headertables loeschen
  677.   {
  678.     if (d->htablep[i])
  679.     {
  680.       d->htablep[i]->give_elements(pos,d->anf,d->ende);
  681.       delete d->htablep[i];                         
  682.     }
  683.     i++;
  684.   }
  685.  
  686.   for (i=0 ; i<d->n ; i++)
  687.   { 
  688.     l_stratified_ptr l_bot_ptr=l_stratified_ptr(s[i].info());
  689.     if  (l_bot_ptr)
  690.       if (l_bot_ptr->size()<=2) 
  691.         delete l_bot_ptr;
  692.       else
  693.       { 
  694.         stratified_ptr bot_ptr=stratified_ptr(s[i].info());
  695.         delete bot_ptr;
  696.       }
  697.   }
  698.  
  699.   free ((char*)d->htablep) ;             // Speicher freigeben
  700.  
  701.   if (d->anf)
  702.     delete d->anf;
  703.  
  704.   delete s;
  705.  
  706.   d->n = 0;                              // Leerinitialisierung
  707.   d->M=4;
  708.   d->sM=13;
  709.   d->k=random(1,maxprim-1);
  710.   d->bed=-17;
  711.   d->htablep=(htp*) calloc(d->sM,sizeof(htp));
  712.   d->anf = d->wo = d->ende = 0;
  713.  
  714. }
  715.